package sword.chapter1Integer;

import java.util.Arrays;

/**
 * 前n个数字二进制形式中1的个数
 * 利用 i & (i-1)的特性可以将i最右边的1置零，运算多少次可以置零，就有多少个1
 *
 * @author K
 * @date 2021-10-10 21:20
 */
public class S3CountBits {

    public static int[] countBits2(int num) {
        int[] result = new int[num + 1];
        for (int i = 0; i <= num; ++i) {
            int j = i;
            while (j != 0) {
                result[i]++;
                j = j & (j - 1);
            }
        }

        return result;
    }

    public static int[] countBits(int num) {
        int[] result = new int[num + 1];
        for (int i = 1; i <= num; ++i) {
            result[i] = result[i & (i - 1)] + 1;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] result = countBits(8);
        Arrays.stream(result).forEach(System.out::println);
        System.out.println("======================================");
        int[] result2 = countBits2(8);
        Arrays.stream(result2).forEach(System.out::println);

    }
}
